package com.rr.middle;

import com.rr.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhuangcanrun
 * @Date 2022/05/19/22:55
 * @description
 **/

public class LevelOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        getAns(root, 0, ans);
        reverseList(ans);
        return ans;
    }

    private void reverseList(List<List<Integer>> ans) {
        int size = ans.size();
        for (int i = 0; i < size; i++) {
            if (i % 2 == 1) {
                List<Integer> an = ans.get(i);
                List<Integer> reverseList = new ArrayList<>();
                for (int j = an.size() - 1; j >= 0; j--) {
                    reverseList.add(an.get(j));
                }
                ans.add(i, reverseList);
                ans.remove(i + 1);
            }
        }
    }

    private void getAns(TreeNode root, int depth, List<List<Integer>> ans) {
        if (root == null) {
            return;
        }
        List<Integer> currentList = ans.size() == depth ? new ArrayList<>() : ans.get(depth);
        if (currentList.size() == 0) {
            ans.add(currentList);
        }
        currentList.add(root.val);
        getAns(root.left, depth + 1, ans);
        getAns(root.right, depth + 1, ans);
    }
}
